package com.breeze.leetcode.swordoffer;

import com.breeze.utils.TreeNode;
import com.breeze.utils.TreeUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 * 剑指 Offer 07. 重建二叉树
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 */
public class Offer07 {
    static class Solution {

        /**
         * 前序：根左右
         * 中序：左根右
         * 时间复杂度：O(n) 每个节点都会处理一次，故O(n)
         * 空间复杂度：O(n) Map占用了O(n)的空间，栈深度为O(logn)，故最终为O(n)
         */
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0) {
                return null;
            }
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return buildTree(preorder, 0, 0, preorder.length, map);
        }

        private TreeNode buildTree(int[] preorder, int preStartIndex, int inStartIndex, int len, Map<Integer, Integer> indexMap) {
            // 递归退出条件，节点树为空或者1个
            if (len <= 0) {
                return null;
            }
            if (len == 1) {
                return new TreeNode(preorder[preStartIndex]);
            }

            // 前序中找到根
            int rootValue = preorder[preStartIndex];
            // 中序中定位根即可确定左右子树
            int rootIndexOfIn = indexMap.get(preorder[preStartIndex]);
            int lLen = rootIndexOfIn - inStartIndex;
            int rLen = len - lLen - 1;
            int lPreStartIndex = preStartIndex + 1;
            int lInStartIndex = inStartIndex;
            int rPreStartIndex = lPreStartIndex + lLen;
            int rInStartIndex = rootIndexOfIn + 1;

            // 递归左右子树
            TreeNode node = new TreeNode(rootValue);
            node.left = buildTree(preorder, lPreStartIndex, lInStartIndex, lLen, indexMap);
            node.right = buildTree(preorder, rPreStartIndex, rInStartIndex, rLen, indexMap);
            return node;
        }
    }

    public static void main(String[] args) {
        test();
    }

    private static void test() {
        Solution solution = new Solution();
        int[] preOrder = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
        int[] midOrder = new int[]{4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode treeNode = solution.buildTree(preOrder, midOrder);
        TreeUtils.showLevelOrder(treeNode);
        TreeUtils.showPostOrder(treeNode);
    }
}
